#include <iostream>
#include <vector>
using namespace std;


class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
        {
            return 0;
        }
        if (n == 1)
        {
            return nums[0];
        }
        vector<int> ret(n, 0);
        ret[0] = nums[0];
        ret[1] = max(nums[0], nums[1]);
        for (int i = 2; i < n; i++)
        {
            ret[i] = max(ret[i - 1], ret[i - 2] + nums[i]);
        }
        return max(ret[n - 2], ret[n - 1]);
    }
};


class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
        {
            return 0;
        }
        if (n == 1)
        {
            return nums[0];
        }
        vector<int> ret1(n, 0);
        vector<int> ret2(n - 1, 0);
        ret1[1] = nums[1];
        ret2[0] = nums[0];
        for (int i = 2; i < n; i++)
        {
            ret1[i] = max(ret1[i - 1], ret1[i - 2] + nums[i]);
        }
        for (int i = 2; i < n - 1; i++)
        {
            ret2[i] = max(ret2[i - 1], ret2[i - 2] + nums[i]);
        }
        return max(ret1[n - 1], ret2[n - 2]);
    }
};